package com.note.feng.leetcode.algorithms.easy.linked;

import java.util.Stack;

public class TwoHundredSix {

    /**
     * 206 反转链表
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     *
     * 示例 1：
     *
     * 输入：head = [1,2,3,4,5]
     * 输出：[5,4,3,2,1]
     * 示例 2：
     *
     * 输入：head = [1,2]
     * 输出：[2,1]
     * 示例 3：
     *
     * 输入：head = []
     * 输出：[]
     *
     * 提示：
     *
     * 链表中节点的数目范围是 [0, 5000]
     * -5000 <= Node.val <= 5000
     *
     * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/reverse-linked-list
     */
    /**
     *解法：迭代
     * 在遍历链表时，将当前节点的 \textit{next}next 指针改为指向前一个节点。由于节点没有引用其前一个节点，
     * 因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode node = head;
        while (node != null){
            ListNode listNode = head.next;
            node.next = pre;
            pre = node;
            node = listNode;
        }
        return node;
    }

    /**
     * 递归版本稍微复杂一些，其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？
     *
     * 假设链表为：
     *
     * n_1\rightarrow \ldots \rightarrow n_{k-1} \rightarrow n_k \rightarrow n_{k+1} \rightarrow \ldots \rightarrow n_m \rightarrow \varnothing
     * n
     * 1
     * ​
     *  →…→n
     * k−1
     * ​
     *  →n
     * k
     * ​
     *  →n
     * k+1
     * ​
     *  →…→n
     * m
     * ​
     *  →∅
     *
     * 若从节点 n_{k+1}n
     * k+1
     * ​
     *   到 n_mn
     * m
     * ​
     *   已经被反转，而我们正处于 n_kn
     * k
     *
     * n_1\rightarrow \ldots \rightarrow n_{k-1} \rightarrow n_k \rightarrow n_{k+1} \leftarrow \ldots \leftarrow n_m
     * n
     * 1
     * ​
     *  →…→n
     * k−1
     * ​
     *  →n
     * k
     * ​
     *  →n
     * k+1
     * ​
     *  ←…←n
     * m
     *
     * 我们希望 n_{k+1}n
     * k+1
     * ​
     *   的下一个节点指向 n_kn
     * k
     *
     * 所以，n_k.\textit{next}.\textit{next} = n_kn
     * k
     * ​
     *  .next.next=n
     * k
     *
     * 需要注意的是 n_1n
     * 1
     * ​
     *   的下一个节点必须指向 \varnothing∅。如果忽略了这一点，链表中可能会产生环
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode node = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }

    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
